class Solution 
{
    //思路就是对于我们每个位置我们可以选或者不选
public:
    int help(vector<int>&nums,int left, int right)
    {
        if(left>right) return 0;
        vector<int>dp1(nums.size());
        auto dp2=dp1;
        dp1[left]=nums[left];
        for(int i=left+1;i<=right;i++)
        {
            dp1[i]=dp2[i-1]+nums[i];
            dp2[i]=max(dp1[i-1],dp2[i-1]);
        }
        return max(dp1[right],dp2[right]);
    }
    int rob(vector<int>& nums) 
    {
        int n=nums.size();
        int ret1=nums[0]+help(nums,2,n-2);
        int ret2=help(nums,1,n-1);
        return max(ret1,ret2);
    }
};